package suanfa;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
//7.列举一个贪心算法解决问题的例子。
public class Greedyalgorithm {
    public static void main(String[] args) {
        HashMap<String, HashSet<String>> bc=new HashMap<>();

        HashSet<String> k1=new HashSet<>();
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");

        HashSet<String> k2=new HashSet<>();
        k2.add("广州");
        k2.add("北京");
        k2.add("深圳");

        HashSet<String> k3=new HashSet<>();
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");

        HashSet<String> k4=new HashSet<>();
        k4.add("上海");
        k4.add("天津");

        HashSet<String> k5=new HashSet<>();
        k5.add("杭州");
        k5.add("大连");

        bc.put("k1",k1);
        bc.put("k2",k2);
        bc.put("k3",k3);
        bc.put("k4",k4);
        bc.put("k5",k5);

        HashSet<String> allareas=new HashSet<>();
        allareas.add("北京");
        allareas.add("上海");
        allareas.add("天津");
        allareas.add("广州");
        allareas.add("深圳");
        allareas.add("成都");
        allareas.add("杭州");
        allareas.add("大连");


        HashSet<String> tempset=new HashSet<>();
        ArrayList<String> selects=new ArrayList<>();
        String maxkey=null;
        int maxsize=0;
        while(allareas.size()!=0){
            maxkey=null;
            maxsize=0;
            for(String k:bc.keySet()){
                tempset.clear();
                HashSet<String> areas=bc.get(k);
                tempset.addAll(areas);
                tempset.retainAll(allareas);
                int csize=tempset.size();
                if(csize>0&&(csize>maxsize||(csize==maxsize &&maxkey==null))){
                    maxkey=k;
                    maxsize=csize;
                }
            }
            if(maxkey!=null){
                selects.add(maxkey);
                allareas.removeAll(bc.get(maxkey));
            }
        }

        /*原方程
        HashSet<String> tempset=new HashSet<>();
        ArrayList<String> selects=new ArrayList<>();
        String maxkey=null;
        while(allareas.size()!=0){
            maxkey=null;
            for(String k:bc.keySet()){
                tempset.clear();
                HashSet<String> areas=bc.get(k);
                tempset.addAll(areas);
                tempset.retainAll(allareas);
                if(tempset.size()>0&&(maxsize==null||tempset.size()>bc.get(maxkey).size()){
                    maxkey=k;
                }
            }
            if(maxkey!=null){
                selects.add(maxkey);
                allareas.removeAll(bc.get(maxkey));
            }
        }
         */
        System.out.println("得到的选择结果："+selects);//k1,k2,k3,k5
    }
}
